package wj.d902;

import java.util.Arrays;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class bfs {
    public int[][] dfs(int[][] board) {
        int h = board.length;
        int w = board[0].length;
        int[][] result = new int[h][w];

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (board[i][j] == 1) {
                    result[i][j] = bfs(board, h, w, i, j);
                } else {
                    result[i][j] = 0;
                }
            }
        }
        return result;
    }

    // 进行横向和纵向广度优先遍历
    private int bfs(int[][] board, int h, int w, int i, int j) {
        int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //上下左右四个方向
        int[][] visited = new int[h][w];
        Queue<int[]> queue = new LinkedBlockingQueue<>();
        visited[i][j] = 1;
        queue.add(new int[]{i, j, 0});
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            for (int[] direct : directions) {
                int x = pos[0] + direct[0];
                int y = pos[1] + direct[1];
                if (0 <= x && x < h && 0 <= y && y < w && visited[x][y] == 0) {
                    if (board[x][y] == 0) {
                        return pos[2] + 1;
                    } else {
                        visited[x][y] = 1;
                        queue.offer(new int[]{x, y, pos[2] + 1});
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[][] board = new int[][]{
                {0, 0, 0},
                {0, 1, 0},
                {1, 1, 1}
        };
        int[][] result = new bfs().dfs(board);
        for (int[] r : result) {
            Arrays.stream(r).forEach(a -> System.out.print(a + ","));
            System.out.println();
        }
    }
}
